package com.example.leetcode.prcatice;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
 *
 * 子数组 是数组中 连续 的一部分。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test862 {


    public int shortestSubarray(int[] nums, int k) {
        int len = nums.length;
        long[] prefixSum = new long[len + 1];
        for (int i = 0;i<=len; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        int r = len + 1;
        Deque<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0;i<= len; i++) {
            long cur = prefixSum[i];
            while (!queue.isEmpty() && cur - prefixSum[queue.peekFirst()] >=k) {
                r = Math.min(r, i - queue.pollFirst());
            }
            while (!queue.isEmpty() && cur <= prefixSum[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return r > len ? -1 : r;
    }
}
